#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

/**
 * @方法: 双指针 + 剪枝
 * @时间复杂度: o(n^3)
 * @空间复杂度: o(1)
 * @评价: 类似三数之和，但是需要剪枝, 同时防止溢出。
 */
vector<vector<int>> fourSum(vector<int>& nums, int target) {
    int n = nums.size();
    sort(nums.begin(),nums.end());
    vector<vector<int>> ans;

    for(int i=0;i<n;i++){
        if(i > 0 && nums[i] == nums[i-1]) continue;
        for(int j=i+1;j<n;j++){
            if(j > i+1 && nums[j] == nums[j-1]) continue;
            int p = n-1;
            for(int k=j+1;k<n;k++){
                if(k > j+1 && nums[k] == nums[k-1]) continue;
                while(k < p && nums[i] + nums[j] > target-nums[p] - nums[k]){
                    p--;
                }
                if(k == p) break;
                if(nums[i] + nums[j] == target-nums[k]-nums[p])
                    ans.push_back({nums[i], nums[j], nums[k], nums[p]});
            }
        }
    }
    return ans;
}

int main() {
    cout << "hello world" << endl;


    return 0;
}